#include <vector>
#include <iostream>
using namespace std;

class Node {
public:
  // 当我们给一个方法定义默认参数的时候，
  // 必须要从右向左定义
  Node(int v, Node *l = nullptr, Node *r = nullptr)
    :value(v), left(l), right(r) {}
  ~Node() { cout << "Node was destroyed" << endl; }

public:
  int value;
  Node *left;
  Node *right;
};
// Binary Search Tree
// 1. 每个节点只有两个分叉
// 2. 对于树里的每一个节点，它的左子树的值都小于它，右子树的值都大于它
class BST {
public:
  BST() : root(nullptr) {}

  BST(const vector<int> &v) : root(nullptr) {
    // 用 v 中的每一个数字构造一个二叉树
    root = put(nullptr, v[0]);

    for (int i = 1; i < v.size(); ++i) {
      put(root, v.at(i));
    }
  }

  Node *min() {
    if (root == nullptr) {
      return nullptr;
    }

    Node *p = root;

    while (p->left != nullptr) {
      p = p->left;
    }

    return p;
  }

  Node *max() {
    if (root == nullptr) {
      return nullptr;
    }

    Node *p = root;

    while (p->right != nullptr) {
      p = p->right;
    }

    return p;
  }

  void deleteMin() {
    // 1. 确保删除之后 BST 里的指针关系正确
    deleteMinHelper(root);
  }

private:
  // 从 pNode 指向的节点求 BST 的最小值
  Node *deleteMinHelper(Node *pNode) {
    if (pNode->left == nullptr) {
      Node *p = pNode->right;
      delete pNode;
      return p;
    }
    
    pNode->left = deleteMinHelper(pNode->left);
    return pNode;
  }

  // 返回值  -  挂在哪个节点的下面
  // 插入位置 - 以什么地方为起点开始插入
  // 永远都只在叶子结点的位置插入元素
  Node *put(Node *p/*插入位置*/, int v/*要插入的值*/) {
    if (p == nullptr) {
      return new Node {v};
    }

    if (v < p->value) {
      // 在 p 的左子树中插入
      p->left = put(p->left, v);
    }
    else if (v > p->value) {
      p->right = put(p->right, v);
    }
    else {
      // 什么都不做
    }

    return p;
  }
private:
  Node *root;
};

int main(int argc, char const *argv[])
{
  Node *p = nullptr;

  if (1) {
    // 从函数的栈空间创建
    Node n {6};
    p = &n;
  }
  
  cout << p->value << endl;
  if (p->left == nullptr) {
    cout << "Empyt left" << endl;
  }
  
  Node *pNode = nullptr;
  if (1) {
    // 从操作系统的堆空间中创建
    pNode = new Node {6};
  }

  cout << pNode->value << endl;
  
  delete pNode;

  BST bst; // 空的二叉树
  vector<int> v {9, 1, 5, 2, 7, 6, 8};
  BST bst1 {v};
  return 0;
}

